Today bar codes are ubiquitously found on or associated with objects of various types, such as the packaging of retail, wholesale, and inventory goods; retail product presentation fixtures (e.g., shelves); goods undergoing manufacturing; personal or company assets; and documents. By encoding information, a bar code typically serves as an identifier of an object, whether the identification be to a class of objects (e.g., oranges) or a unique item (e.g., U.S. Pat. No. 6,012,639). FIG. 1A depicts a segment of a typical bar code 100, with alternating bars (i.e., dark areas) 102 and spaces (i.e., light areas) 104. The positions of the bars 102 and spaces 104 encode particular information. More specifically, the widths of the bars 102 and spaces 104 are often set to encode a desired information sequence, as the pattern of bars and spaces represents a string of binary ones and zeros, wherein the width of any particular bar or space is an integer multiple of a specified minimum width, which is called a “module” or “unit.” Thus, to decode the information, a bar code reader must be able to reliably discern the edge locations of the bars 102 and the spaces 104. The leading edge of a bar (i.e., a light-to-dark transition) is commonly denoted as an STV (set video), and the trailing edge of a bar (i.e., a dark-to-light transition) is commonly denoted as an RTV (reset video). The first several STVs and RTVs of the bar code 100 are labeled in FIG. 1A, assuming (arbitrarily) that the bar code is scanned from left to right.
Optical scanning equipment can be utilized to generate an electrical signal indicative of the positions of bars and spaces in a bar code. Such a signal, denoted x(t), is depicted in simplified form in FIG. 1B for the corresponding bar code 100. Before describing the processing of the signal x(t), a brief description of the optical scanning equipment that generates that signal is helpful. A more complete introduction to the optical scanning of bar codes can be found in the background section of the above-noted U.S. Pat. No. 6,102,639, the entirety of which is incorporated by reference herein. Typical optical scanning equipment comprises one or more illumination sources and one or more photodetectors. The illumination source may be a laser producing a focused beam spot on a small area of the bar code 100. As the laser spot and the bar code 100 move relative to each other, such that the spot is scanned across the bar code 100, a photodetector detects the laser light reflected off the bar code 100 and produces an electrical signal whose magnitude is related to the optical power of the reflected signal. Thus, as the spot scans across the bar code 100, the photodetector generates an electrical signal whose variations over time at least roughly correlate to the spatial pattern of bars 102 and spaces 104 in the bar code 100. Alternatively, the illumination source may be diffuse across the entire bar code 100, and the bar code may be imaged using a charge-coupled device (CCD) camera or a CMOS (complementary metal-oxide-semiconductor) imager, either of which forms an electronic image of the bar code 100. That electronic image can be sampled in the forward direction of the bar code 100 to generate a virtual scan line signal, much like the scan line signal generated with a scanning laser spot. In any event, the result is an electronic signal, which, at least ideally, somehow relates to the spatial positions of the bars 102 and spaces 104 in the bar code 100. The next step is to process that signal to determine with some reliability where the edges (STVs and RTVs) lie.
FIG. 2 is schematic diagram of a conventional edge detection system 200 for processing the scan line signal x(t) illustrated in FIG. 1B. The system 200 performs edge detection using a typical gated peak detection scheme. In general functional terms, the system 200 operates by forming the first and second derivatives of the scan line signal x(t) and by detecting zero crossings of the second derivative, which ideally represent optical edges. Moreover, the system 200 qualifies zero crossings of the second derivative only if the first derivative exceeds a threshold. In terms of hardware, the system 200 includes a double differentiator 220, an envelope detector 230, three comparators 240, 242, and 246, and two logical AND gates 250 and 255. The hardware operates as follows: As a preliminary matter, a preamplifier (not shown) may amplify, buffer, invert and/or condition the scan line signal x(t), which is received at the input of the differentiator 220. The differentiator 220 produces a first derivative signal x′(t) and second derivative signal x″(t), respectively. While it is also possible to generate the first and second derivative signals x′(t) and x″(t) using two separate single differentiators, it is preferable to use common hardware to produce both to ensure more easily that x′(t) are x″(t) are time-aligned, as described in U.S. Pat. No. 6,073,849, which is incorporated herein by reference. The envelope detector 230 processes the first derivative signal x′(t) to determine, based on the extreme maximum and minimum values of that signal, a threshold value T somewhat smaller in magnitude than those extreme values. One example of a suitable implementation of the envelope detector 230 is disclosed in U.S. Pat. No. 4,000,397, which is incorporated herein by reference. By comparing the first derivative signal x′(t) to that threshold value, the comparators 240 and 242 detect peaks in that signal and produce respective logical true-valued outputs yS(t) and yR(t) when the first derivative signal x′(t) exceeds the threshold value. Because sharp transitions in the value of the scan signal x(t) should produce peaks in the first derivative signal x′(t), either yS(t) and yR(t) should be a logical true value during such peaks (yS(t) being true during a minimum or negative peak, and yR(t) being true during a maximum or positive peak). Because the second derivative signal should cross zero at such peaks, the comparator 246 is configured to detect those zero crossings and enable the appropriate AND gate 250 or 255, respectively, to generate the STV or RTV signal, such that only one of which is true at any given time.
Further insight into the operation of the system 200 can be gleaned by returning to FIG. 1, in which FIGS. 1B–1H are voltage-versus-time plots for various signals in the system 200. FIG. 1B, as already noted, is a plot of the scan line signal x(t), which is derived from a photodetector current, which is generally at a higher value during the spaces 104 and a lower value during the bars 102, as more light is reflected from the spaces 104 than the bars 102. (Depending upon the optical scanning equipment, that relationship may be reversed.) However, the scan line signal x(t) is not a perfect representation of the bar code 100 for a variety of reasons discussed below. FIG. 1C is a plot of the first derivative signal x′(t), including the threshold levels +T and −T. FIG. 1D is the second derivative signal x″(t), which, as one can see, crosses zero whenever the x′(t) is at a peak. FIG. 1E shows the signal yS(t), the output of the comparator 240. As can be seen, assuming high-true logic levels, as utilized in this figure, yS(t) is high when x′(t)<−T. Similarly, FIG. 1F shows the signal yR(t), the output of the comparator 242, which is high when x′(t)>+T. Finally, FIGS. 1G and 1H are plots of the RTV and STV signals, respectively, which are the logical AND combination of yR(t) and the condition that x″(t)<0, and yS(t) and the condition that x″(t)>0.
As the inventors have recognized, a shortcoming of the system 200 is that the STV and RTV signals may contain multiple pulses for a single transition in the bar code 100 and thus do not unambiguously indicate edge positions in the bar code 100. This is due to the fact that more than one peak can occur in the first derivative signal x′(t) for a single real edge in the bar code 100—a phenomenon that can be called “peak multiplication.” There are several reasons why more than one peak may appear in x′(t) for a given real transition edge. Some reasons are attributable to the optical scanner. For example, the spot profile of the laser beam may have multiple peaks. Another reason may be noise introduced by the optical scanner or the electronic circuitry. Other reasons are traceable to external factors, including poor bar code printing quality, poor substrate quality or roughness, inconsistent bar or space color, modulated lighting effects, etc. Regardless of the cause, each local first derivative peak is detected as a separate like edge by the system 200. However, multiple adjacent edges of the same type (STV or RTV) cannot be legitimate, as adjacent edges must be of alternating types. Only one edge in such a group is the best estimate of the true edge position.
Other edge detection techniques suffer from the same problem. For example, multi-bit digitizers, such as the systems disclosed in U.S. Pat. Nos. 5,302,813, 5,449,893, and 5,734,152, which operate by digitizing the first derivative peaks for an entire scan line and then applying various thresholds to the entire digitized record until a decodable peak pattern results, perform poorly in the presence of ISI (inter-symbol interference) and do not inherently ensure that multiple adjacent edges are rejected.
Bar codes are just one example of the many types of optical codes in use today. In general, optical codes encode useful, optically-readable information about the items to which they are attached or otherwise associated. While bar codes generally encode information across one dimension, higher-dimensional optical codes are also possible, such as, two-dimensional matrix codes (e.g., MaxiCode) or stacked codes (e.g., PDF 417). Decoding binary optical codes in general poses the same challenges, such as peak multiplication, posed by bar codes in particular.